Embodiments of the present invention relate generally to video hosting systems, and more particularly to recommending appropriate music soundtracks for videos in a video hosting system.